/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
#include <stdlib.h>
#include "priorityqueue.h"
#include "testutil.h"

/*
 * Structures definitions
 */
 
struct priorityqueue_node {
	int key;
	void *data;
};

struct priorityqueue_adt {
	int length;
	int max_length;
	
	struct priorityqueue_node item[1];	
};

/*
 * Private functions
 */
static void heapify(PriorityQueue pqueue, int i) {
	int l, r, smallest;
	PQItem item;
	l = Left(i);
	r = Right(i);
	smallest = (l < pqueue->length && 
				(pqueue->item[l]).key) < (pqueue->item[i]).key) ? l : i;
	smallest = (r < pqueue->length &&
				(pqueue->item[r]).key) < (pqueue->item[smallest]).key) ? r : smallest;
   if (smallest != i) {
      item = pqueue->item[smallest];
      pqueue->item[smallest] = pqueue->item[i];
      pqueue->item[i] = item;
      heapify(pqueue, smallest);
   }
}
 
/* find minimum item */
#define PQ_Min(pqueue)		(pqueue->item[0])
#define PQ_MinKey(pqueue)	(PQ_Min(pqueue).key)
#define PQ_MinData(pqueue)	(PQ_Min(pqueue).data)

/* internal opperation */
#define Parent(i) (((i) - 1) / 2)
#define Left(i)   ((i) * 2 + 1)
#define Right(i)  ((i) * 2 + 2)

 /*
 * Public functions
 */
PriorityQueue PQ_New(int maxLength) {
	PriorityQueue pqueue;
	
	pqueue = malloc(sizeof(PriorityQueue)
			+ (maxLength - 1) * sizeof(struct priorityqueue_node));
	
	CHECK_FATAL(this != 0);
	
	pqueue->length = 0;
	pqueue->max_length	= maxLength;
	
	return (pqueue);
}


void PQ_Free(PriorityQueue pqueue) {
	free(pqueue);
}


void PQ_Insert(PriorityQueue pqueue, PQItem item) {
	
	int i, key = item.key;
	
	CHECK_FATAL(pqueue->length < pqueue->max_length);
	pqueue->length++;
	
	i = pqueue->length - 1;
	
	while(i > 0 && (pqueue->item[Parent(i)]).key > key) {
		pqueue->item[i] = pqueue->item[Parent(i)];
		i = Parent(i);
	}
	
	pqueue->item[i] = item;
}


PQItem PQ_ExtractMin(PriorityQueue pqueue) {
	return PQ_Min(pqueue);
}


int PQ_ExtractMinKey(PriorityQueue pqueue) {
	return PQ_MinKey(pqueue);
}


void* PQ_ExtractMinData(PriorityQueue pqueue) {
	return PQ_MinData(pqueue);
}


void PQ_DeleteMin(PriorityQueue pqueue) {
	CHECK_FATAL(pqueue->length > 0);
	pqueue->length--;
	pqueue->item[0] = pqueue->item[pqueue->length];
	heapify(pqueue,0);
}


int PQ_Length(PriorityQueue pqueue) {
	return pqueue->length;
}

